package 极客算法训练营.chapter09;

import java.util.ArrayDeque;
import java.util.Deque;

public class 扫雷游戏 {
    class Solution {
        public char[][] updateBoard(char[][] board, int[] click) {
            if (board == null || board.length == 0) {
                return board;
            }
            int[] dx = {-1, -1, -1, 0, 1, 1, 1, 0};
            int[] dy = {-1, 0, 1, 1, 1, 0, -1, -1};
            int rowSize = board.length;
            int colSize = board[0].length;
            int x = click[0];
            int y = click[1];

            boolean[][] visited = new boolean[rowSize][colSize];
            visited[x][y] = true;

            //点到地雷直接死
            if (board[x][y] == 'M') {
                board[x][y] = 'X';
                return board;
            }

            //没有点到地雷
            Deque<Integer> queue = new ArrayDeque<>();
            queue.add(x * colSize + y);

            while (!queue.isEmpty()) {
                int size = queue.size();
                for (int i = 0; i < size; i++) {
                    Integer poll = queue.poll();
                    int X = poll / colSize;
                    int Y = poll % colSize;
                    //对每一层元素，进行八个方向的扫描,判断附近有几个雷
                    int count = 0;
                    for (int m = 0; m < 8; m++) {
                        int newX = X + dx[m];
                        int newY = Y + dy[m];
                        //判断是否越界
                        if (newX < 0 || newY < 0 || newX >= rowSize || newY >= colSize) {
                            continue;
                        }
                        if (!visited[newX][newY] && board[newX][newY] == 'M') {
                            count++;
                        }
                    }
                    //如果有雷就标记为数量
                    if (count > 0) {
                        board[X][Y] = (char) (count + '0');
                        visited[X][Y] = true;
                    } else {
                        //如果没有雷就设为安全区域“B”，并延伸搜索
                        board[X][Y] = 'B';
                        visited[X][Y] = true;
                        for (int m = 0; m < 8; m++) {
                            int newX = X + dx[m];
                            int newY = Y + dy[m];
                            //判断是否越界,是否访问过
                            if (newX < 0 || newY < 0 || newX >= rowSize || newY >= colSize || visited[newX][newY]) {
                                continue;
                            }
                            visited[newX][newY] = true;
                            queue.add(newX * colSize + newY);
                        }
                    }
                }
            }
            return board;
        }
    }
}
